package LeetCode刷题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-19 15:29
 * @description: Functions of this class is
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 *
 * 官方解法：（双指针+排序）
 * class Solution {
 *     public List<List<Integer>> threeSum(int[] nums) {
 *         int n = nums.length;
 *         Arrays.sort(nums);
 *         List<List<Integer>> ans = new ArrayList<List<Integer>>();
 *         // 枚举 a
 *         for (int first = 0; first < n; ++first) {
 *             // 需要和上一次枚举的数不相同
 *             if (first > 0 && nums[first] == nums[first - 1]) {
 *                 continue;
 *             }
 *             // c 对应的指针初始指向数组的最右端
 *             int third = n - 1;
 *             int target = -nums[first];
 *             // 枚举 b
 *             for (int second = first + 1; second < n; ++second) {
 *                 // 需要和上一次枚举的数不相同
 *                 if (second > first + 1 && nums[second] == nums[second - 1]) {
 *                     continue;
 *                 }
 *                 // 需要保证 b 的指针在 c 的指针的左侧
 *                 while (second < third && nums[second] + nums[third] > target) {
 *                     --third;
 *                 }
 *                 // 如果指针重合，随着 b 后续的增加
 *                 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
 *                 if (second == third) {
 *                     break;
 *                 }
 *                 if (nums[second] + nums[third] == target) {
 *                     List<Integer> list = new ArrayList<Integer>();
 *                     list.add(nums[first]);
 *                     list.add(nums[second]);
 *                     list.add(nums[third]);
 *                     ans.add(list);
 *                 }
 *             }
 *         }
 *         return ans;
 *     }
 * }
 **/
public class NoNo三数之和 {
    public static void main(String args[]){
        System.out.println(threeSum(new int[]{-1,0,1,2,-1,-4,-2,-3,3,0,4}));
    }
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        int len=nums.length;
        Arrays.sort(nums);
        if(len<3||nums==null){
            return ans;
        }
        for(int first=0;first<len;++first){
            if(first>0&&nums[first]==nums[first-1]){
                continue;
            }
            int third=len-1;
            int target=-nums[first];
            for(int second=first+1;second<len;++second){
                if(second>first+1&&nums[second]==nums[second-1]){
                    continue;
                }
                while(second<third&&nums[second]+nums[third]>target){
                    --third;
                }
                if(second==third){
                    break;
                }
                if(nums[second]+nums[third]==target){
                    List<Integer> sub=new ArrayList<Integer>();
                    sub.add(nums[first]);
                    sub.add(nums[second]);
                    sub.add(nums[third]);
                    ans.add(sub);
                }
            }
        }
        return ans;
    }
}